1. Field of the Invention
The present invention relates generally to data driven type information processors, and more particularly, to data driven type information processors capable of processing a plurality of different data packet groups in parallel in accordance with the same data flow program.
2. Description of the Background Art
In a conventional von Neuman computer, various types of information are stored as a program in a program memory in advance, and addresses in the program memory are sequentially specified by a program counter so that the instructions are sequentially read out, the instructions are executed.
On the other hand, a data driven type information processor is one type of non-von-Neuman computers do not perform with sequential execution of instructions by a program counter. Such data driven type information processor employs architecture based on parallel processing of instructions. In the data driven type information processor wherein an execution of an instruction is enabled upon collection of data to be operated, a plurality of instructions are simultaneously driven by data, so that programs are executed in parallel in accordance with a natural flow of the data. As a result, it is considered that the time required for the operation will be drastically reduced.
FIG. 10 is a block diagram showing the structure of one example of a conventional data driven type information processor. FIG. 11 is a diagram showing a field structure of a data packet to be applied to a conventional data driven type information processor and that of one embodiment of the present invention. FIG. 10 is a diagram showing the structure of a memory in a paired data detecting unit to be applied to the conventional data driven type information processor and that of one embodiment of the present invention.
In FIG. 11, a data packet PD includes a flag field F1, a destination field F2, a generation number field F3, an instruction field F4, a data 1 field F5 and a data 2 field F6. The field F1 stores a 2-operand flag 106 and a flag 107 indicative of unfiring (hereinafter referred to as an unfiring flag), the field F2 stores node number data "node", the field F3 stores generation number data "CD", the field F4 stores an operation instruction OP, and the field F5 or F6 stores operand data D1 or D2. More detailed description will be made of each data and flag stored in a data packet PD later.
The data driven type information processor shown in FIG. 10 includes a junction unit 10 for outputting applied data packets in the order of application, a program storing unit 11 for storing a data flow program in advance, a paired data detecting unit 12a including a memory 600, an operation processing unit 14, a branch unit 15 and a data buffer 16. Junction unit 10 inputs applied data packets and outputs the same to program storing unit 11 in due order. Program storing unit 11 stores in advance a data flow program including a plurality of records which store destination information (node number data and generation number data) and instruction information (operation instructions). Program storing unit 11 reads out destination information and instruction information in a subsequent order from the data flow program by addressing based on node number data "node" in the applied data packet PD, stores the destination information and the instruction information in the fields F2 and F4 of the applied data packet, respectively, and outputs the input data packet PD.
Memory 600 of paired data detecting unit 12a will be described in the following. The structure of memory 600 is shown in FIG. 12. Memory 600 has a physical space accessible by addressing based on node number data "node" of a data packet PD input to detecting unit 12a. Each addressing domain stores a valid flag 105 and matching data or empty data (data indicative of nothing). Matching data includes matching generation number data CD1, a matching operation instruction OP1 and matching operand data D3. The flag 105 is set only when matching data to be read is stored in a corresponding domain and otherwise it is reset.
Operation of paired data detecting unit 12a will be described assuming that only matching operand data D3 is stored as matching data in memory 600. Paired data detecting unit 12a matches two operand data to be processed for execution of a 2-input instruction (two item operation etc.) in an operation processing unit 14 in a succeeding stage when a flag 106 of an input data packet PD is set. In other words, the paired data detecting unit 12a detects two different data packets PD having the same destination information. When a data packet PD with a flag 106 set is input, paired data detecting unit 12a reads a valid flag 105 stored in an addressing domain of memory 600 by addressing based on the node number data "node" of the input packet PD. At this time, if the read flag 105 is set, which means that data to be paired are already in a matching state in memory 600, the input data packet PD stores operand data D3 in its field F5 or F6, that is, the packet PD stores two different operand data pairs, which input data packet is output to operation processing unit 14. Then, a valid flag 105 corresponding to the matching operand data D3 as data to be paired is reset. Conversely, if the flag 105 stored in the addressing domain is reset, which means that operand data to be paired has not been input, the data of the input data packet PD is written in the addressing domain to set the corresponding flag 105 in the addressing domain, whereby the input data packet PD stands by in memory 600 for input of a data packet PD to be paired.
Operation processing unit 14 inputs a data packet PD applied from paired data detecting unit 12a, performs operation processing for data D1 or D2 stored in the input packet PD based on the operation instruction OP stored in the input data packet PD, stores data indicative of the operation result in the field F5 of the input data packet PD and outputs the input data packet PD to branch unit 15. Branch unit 15 selectively outputs the input data packet PD outside the information processor or to data buffer 16 based on destination information of the input data packet PD from operation processing unit 14. Data buffer 16 inputs applied data packets PD and sequentially outputs the same.
As the data packet PD continues to circulate through program storing unit 11, paired data detecting unit 12a, operation processing unit 14, program storing unit 11, . . . as described in the foregoing, the operation proceeds based on the data flow program stored in program storing unit 11.
A data driven type information processor having a mechanism of processing a plurality of different data packet groups in parallel by using the same data program will be specifically referred to as a dynamic data driven type information processor. A processing operation of the dynamic data driven type information processor will be briefly described in the following. FIGS. 13A and 13B are diagrams for illustrating a processing operation of the dynamic data driven type information processor. As shown in FIG. 13A, for example, consideration will be given to a data flow program which inputs three data of data X1, X2 and X3 to obtain outputs Y1, Y2. It is assumed that in an execution of the program by the dynamic data driven type information processor by using the plurality of data groups including data X1, X2 and X3, another new data group (X1, X2, X3) is input to the information processor after confirming outputs (Y1, Y2) so as to prevent different data groups from being mixed to each other to cause malfunction at the time of data input or during processing. However, with an identifier for distinguishing a data group being input or processed from other data groups being processed, another data group could be input without waiting for the processing of a certain data group to finish. Hereinafter, such identifiers will be referred to as generation numbers and allotted in an ascending order to corresponding data groups to be applied to the information processor in the order of application. Such dynamic data driven type information processor as shown in FIG. 13B can be equipped with a processing mechanism of inputting a plurality of data groups to which different generation numbers are allotted and individually identifying these data groups by the generation numbers to output a correct result while preventing the different data groups from mixing. The following is an example of a data group to which generation numbers are allotted. In a case where data groups, which are obtained by sampling at fixed intervals a plurality of signals which are changed with the lapse of time, are sequentially input to a dynamic data driven type information processor, for example, there exist a plurality of different data packets according to a lapse of "time". In this case, the generation numbers are stored in the field F3 of a data packet PD as generation number data CD.
Description will be made of processing by using generation number data CD at paired data detecting unit 12a. During data processing, an operation is performed between a data packet PD wherein generation number data CD is stored and a data packet PD having the same generation number data CD in order to generate resultant data having the same generation number data CD. Paired data detecting unit 12a therefore should detect data of data packets PD to be paired which have the same generation number data CD and the same node number data "node". Memory 600 desirably has a matching region, that is, a physical memory space, for detecting paired data out of all of combinations of all generation number data CD and node number data "node" to be used. However, with an increase in the number of generations and nodes to be treated, a physical memory space required in memory 600 is expanded, which is neither practical nor economical for an effective use of the memory. Thus, paired data detecting unit 12a processes data packet groups having different generation number data CD such that they share the same queuing region, that is, the same address space in memory 600. In other words, the paired data detecting unit processes data packet groups having different generation number data CD by addressing memory 600 based on an address value (hereinafter referred to as "hash address") obtained as a result of a hash operation of node number data "node" such that even such data packet groups having different generation number data share the same matching region in memory 600. Operation of paired data detecting unit 12a related to the share of the queuing region will be described.
Paired data detecting unit 12a, upon input of an applied data packet PD, reads data from memory 600 by addressing based on a hash address of the input packet PD. In particular, comparison of the generation number data is made, to carry out paired data detection based on the comparison result. More specifically, if the flag 105 read by addressing is at a reset state, data of the input data packet PD is written in the addressing domain as queuing data. However, if the read flag 105 is being set, comparison is made between generation number data CD in the input data packet PD and queuing generation number data CD1 stored in the addressing domain. At this time, if the generation number data are equal to each other, data packets to be paired are detected to reset a flag 105 in the addressing domain. Conversely, if the generation number data are not equal to each other, the priority for the use of the addressing domains (matching regions) is determined based on the comparison result. In more detail, if the input data packet PD has lower priority (generation number data CD is larger than matching generation number data CD1, for example), the input data packet PD is output through detecting unit 12 without being operated. Conversely, when the input data packet PD has higher priority (for example, the generation number data CD is smaller than the matching generation number data CD1), the data of the input data packet PD and the matching data stored in the addressing domain region are exchanged to each other, so that the input data packet is output from paired data detecting unit 12a. At this time, the unfiring flag 107 of the output data packet PD is set. The data packet PD with the unfiring flag 107 set is not processed (passing through) at operation processing unit 14 and program storing unit 11 after being output from paired data detecting unit 12a but continues to circulate inside the information processor until the corresponding match region of memory 600 in paired data detecting unit 12a is vacated or until a data packet to be paired is detected. As described in the foregoing, the dynamic data driven type information processor proceeds with a processing while determining priority for the use of match regions for detecting data packets to be paired based on generation number data CD. A maximum generation number is determined depending on a format of a data packet PD, that is, a bit length of the field F3 for storing generation number data CD. The bit length is in turn determined by a physical size of the information processor, a width of a data line for connecting respective portions and a processing (transmission) rate. When the total number (the number of generations) of data packet groups to be supplied to the dynamic data driven type information processor is smaller than the maximum generation number determined as described above, data packets PD are applied in a conventional manner and generation number data are compared by paired data detecting unit 12a, so that a data packet group, which has been applied prior to the other groups, that is, which has higher processing priority, can reliably receive priority for data processing. On the other hand, when data packet groups larger in number than the generations that a data packet PD can handle are sequentially and continuously applied to and processed by the information processor in accordance with the processing priority although there simultaneously exist a less number of generations in the dynamic data driven type information processor, it is necessary to re-allot once used generation number data CD to other later applied data packet groups. However, if the generation number data CD is re-allotted to a data packet group which is applied later, generation number data CD of the previously applied data packet group might be larger (with lower priority) than the generation number data CD of the later applied data packet group, so that a conventional mere comparison of generation number data will not ensure a data packet group (a data packet group applied previously) to be data-processed prior to the others (given priority for using a queuing region). For the foregoing reasons, in a case where processing resultant data having a certain generation number n is used as a part of input data having a re-allotted generation number n-1 applied later, data to be fired (to be paired), that is, data with the generation number n has lower priority than that with the generation number n-1 in the dynamic data driven type information processor, whereby a matching region of memory 600 can not be used, thereby delaying a processing for the data, so that a matching region required for the processing is kept occupied (hereinafter referred to as "deadlock").